package com.wyp168.leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @ClassName SumSubarrayMinsSolution
 * @Title TODO
 * @Description TODO
 * @Author wyp168
 * @Date 2022/10/28 00:08
 */
public class SumSubarrayMinsSolution {
    public static void main(String[] args) {
        SumSubarrayMinsSolution solution = new SumSubarrayMinsSolution();
        int[] arr = {29959,29867,29822,29704,29676,29650,29577,29488,29286,29255,29232,29207,29071,29034,28925,28849,28731,28693,28624,28606,28591,28397,28357,28308,28295,28210,28119,28090,28004,27903,27845,27830,27777,27736,27640,27540,27506,27428,27341,27308,27182,27152,27122,27029,26928,26872,26796,26765,26663,26597,26580,26530,26498,26475,26436,26406,26382,26312,26213,26134,26088,26025,25943,25912,25875,25845,25810,25702,25638,25614,25531,25524,25488,25470,25444,25402,25283,25262,25121,24988,24958,24886,24769,24697,24635,24595,24490,24456,24453,24346,24313,24248,24200,24148,24107,24052,24044,24021,23970,23908,23897,23835,23752,23741,23714,23661,23596,23545,23509,23470,23439,23409,23350,23215,23166,23155,23100,23024,22923,22825,22793,22627,22613,22536,22450,22383,22312,22268,22205,22175,22136,22028,21971,21900,21824,21769,21726,21583,21546,21513,21494,21428,21327,21264,21254,21174,21140,21112,21000,20921,20902,20830,20817,20783,20735,20657,20616,20573,20485,20378,20363,20305,20259,20210,20114,20002,19846,19785,19747,19667,19645,19622,19610,19580,19542,19516,19454,19392,19310,19277,19194,19131,19090,19004,18883,18845,18791,18781,18668,18591,18518,18475,18368,18331,18310,18287,18217,18114,18092,18048,17990,17964,17912,17836,17740,17704,17630,17613,17573,17428,17356,17341,17300,17260,17180,17174,17126,17071,17041,16866,16850,16828,16672,16618,16577,16499,16407,16357,16318,16293,16202,16150,16075,16041,15948,15921,15844,15843,15785,15764,15668,15626,15579,15473,15387,15255,15190,15139,15062,14996,14954,14918,14907,14902,14867,14851,14817,14799,14751,14720,14536,14506,14474,14353,14303,14280,14185,14107,14012,13932,13858,13781,13585,13563,13533,13451,13412,13362,13249,13208,13181,13064,13037,12961,12926,12892,12786,12731,12611,12573,12506,12502,12496,12470,12443,12370,12262,12182,12153,12069,12000,11847,11806,11781,11708,11687,11593,11550,11445,11372,11329,11308,11291,11268,11241,11191,11027,10982,10879,10862,10776,10695,10603,10502,10464,10350,10338,10305,10273,10176,10124,10094,10038,9953,9935,9812,9786,9743,9728,9508,9472,9383,9349,9236,9215,9130,9124,9042,9008,8988,8901,8833,8809,8780,8716,8580,8462,8334,8321,8305,8280,8257,8246,8137,8077,8043,8016,7984,7955,7927,7906,7746,7663,7653,7572,7542,7530,7489,7420,7390,7361,7337,7245,7210,7188,7175,7096,6898,6846,6745,6675,6569,6478,6427,6363,6284,6260,6243,6206,6154,6135,6078,6061,6017,5995,5917,5863,5836,5793,5763,5743,5678,5572,5532,5459,5384,5341,5299,5251,5231,4995,4933,4861,4740,4672,4625,4496,4445,4361,4282,4215,4135,4097,4028,3917,3862,3711,3553,3498,3410,3388,3384,3288,3279,3244,3221,3181,3171,3150,3060,3035,2975,2965,2834,2760,2637,2584,2533,2440,2383,2311,2285,2255,2211,2192,2121,2054,2010,1964,1850,1724,1642,1577,1411,1409,1332,1296,1265,1256,1220,1195,937,903,880,811,739,720,650,609,547,533,459,434,384,279,231,163,102,78,30,5,52,100,155,217,277,328,389,446,473,546,583,649,702,734,768,857,882,912,1043,1219,1243,1258,1290,1325,1359,1409,1567,1642,1679,1726,1873,1965,2017,2088,2172,2204,2226,2273,2288,2316,2434,2522,2558,2622,2678,2790,2933,2965,3025,3037,3071,3167,3180,3194,3233,3269,3282,3383,3387,3401,3465,3528,3595,3801,3910,4020,4078,4128,4213,4271,4295,4420,4472,4612,4663,4739,4845,4891,4980,5109,5241,5284,5335,5379,5388,5478,5546,5639,5705,5751,5766,5803,5855,5879,5975,6000,6024,6070,6093,6137,6156,6212,6256,6276,6304,6421,6441,6537,6614,6743,6844,6893,7087,7169,7183,7200,7237,7262,7352,7376,7398,7441,7491,7541,7564,7602,7656,7707,7814,7924,7940,7958,8014,8036,8048,8132,8141,8250,8279,8288,8321,8331,8374,8515,8655,8723,8807,8825,8878,8953,8990,9011,9077,9128,9172,9219,9276,9383,9420,9499,9535,9736,9744,9801,9900,9951,10038,10093,10119,10147,10265,10301,10314,10340,10456,10499,10564,10622,10767,10802,10876,10882,10997,11063,11217,11243,11276,11299,11314,11365,11407,11456,11587,11627,11705,11751,11792,11831,11901,12012,12118,12180,12240,12296,12385,12469,12473,12497,12503,12537,12578,12723,12778,12858,12901,12936,13020,13048,13136,13195,13232,13325,13377,13424,13493,13547,13564,13724,13856,13911,13938,14075,14151,14234,14300,14353,14395,14499,14507,14705,14724,14796,14802,14823,14858,14882,14905,14914,14936,14962,15049,15114,15161,15237,15272,15399,15565,15587,15666,15749,15778,15830,15843,15864,15928,16039,16075,16141,16163,16246,16315,16333,16389,16415,16526,16601,16650,16798,16845,16861,16991,17046,17090,17140,17178,17186,17292,17305,17343,17419,17456,17610,17617,17693,17728,17783,17909,17918,17970,18032,18083,18104,18114,18223,18296,18330,18363,18428,18496,18578,18660,18733,18782,18792,18861,18929,19069,19127,19184,19269,19279,19355,19394,19494,19539,19559,19599,19612,19643,19666,19745,19760,19815,19864,20012,20141,20231,20270,20330,20370,20380,20500,20595,20617,20690,20751,20811,20824,20843,20910,20925,21044,21126,21165,21198,21260,21280,21343,21467,21505,21531,21564,21640,21755,21817,21885,21929,22010,22103,22159,22196,22229,22270,22368,22414,22515,22570,22615,22630,22806,22864,22951,23030,23107,23155,23191,23226,23399,23438,23464,23487,23524,23559,23634,23667,23719,23747,23764,23869,23901,23936,24012,24022,24045,24074,24141,24185,24204,24272,24327,24452,24455,24490,24560,24615,24641,24734,24815,24890,24963,25025,25242,25282,25283,25414,25446,25475,25489,25527,25586,25636,25640,25771,25844,25848,25883,25923,26005,26048,26106,26157,26312,26359,26395,26429,26465,26491,26513,26558,26584,26601,26667,26770,26864,26900,26996,27118,27129,27176,27272,27313,27389,27478,27517,27580,27700,27761,27811,27844,27848,27967,28051,28108,28176,28264,28302,28332,28380,28525,28591,28617,28681,28727,28744,28874,28994,29047,29123,29221,29239,29274,29347,29493,29596,29668,29694,29717,29847,29871};
//        int[] arr = {39,108,118,229,241,315,507,523,644,699,749,829,841,921,1072,1138,1175,1238,1341,1479,1542,1609,1651,1693,1799,1847,1888,1915,1979,2007,2028,2062,2068,2153,2205,2217,2273,2283,2347,2404,2485,2549,2654,2715,2813,2831,2866,2905,2931,2947,2988,3033,3061,3136,3246,3287,3381,3446,3512,3528,3630,3690,3714,3746,3820,3841,3894,3913,3972,3995,4023,4042,4137,4302,4364,4492,4535,4592,4699,4849,4882,4913,4972,5119,5151,5214,5279,5322,5360,5565,5699,5709,5757,5835,5899,5953,6109,6144,6207,6400,6523,6550,6615,6655,6702,6794,6814,6879,6900,6910,6996,7027,7062,7132,7254,7261,7340,7439,7484,7567,7586,7630,7726,7791,7998,8027,8118,8237,8290,8324,8327,8361,8377,8428,8488,8492,8507,8535,8586,8609,8630,8687,8808,8891,8956,8990,9038,9156,9256,9355,9378,9454,9467,9582,9614,9675,9693,9737,9785,9802,9837,9919,9939,9960,9987,10077,10091,10139,10276,10336,10409,10424,10507,10601,10755,10843,10890,10946,11071,11141,11155,11210,11338,11383,11418,11546,11564,11598,11671,11707,11817,11898,11946,11972,12112,12127,12170,12175,12252,12278,12336,12387,12401,12436,12469,12518,12583,12671,12728,12741,12810,12832,12964,13038,13105,13122,13195,13220,13251,13439,13631,13660,13737,13792,13858,13881,13937,13998,14024,14135,14183,14249,14274,14347,14420,14514,14562,14599,14701,14752,14820,14838,14848,14887,14976,15056,15132,15159,15227,15287,15317,15333,15342,15361,15465,15483,15734,15777,15808,15884,16061,16109,16134,16217,16298,16327,16336,16420,16440,16488,16609,16716,16750,16795,16825,16961,17028,17072,17122,17142,17163,17222,17246,17303,17322,17385,17492,17540,17571,17632,17641,17752,17819,17876,17895,18079,18107,18158,18200,18273,18312,18386,18415,18424,18505,18564,18643,18688,18701,18833,18855,18887,19067,19166,19214,19293,19455,19458,19532,19584,19665,19715,19831,19865,19906,19948,19968,19983,20033,20042,20061,20116,20223,20296,20388,20444,20556,20579,20615,20654,20770,20843,20881,20907,21025,21083,21118,21301,21392,21454,21531,21584,21626,21715,21780,21810,21825,21863,21952,21970,22010,22062,22140,22172,22206,22253,22321,22325,22344,22378,22437,22512,22542,22597,22658,22713,22823,22826,22897,22901,22949,23015,23068,23094,23160,23359,23382,23442,23496,23524,23589,23616,23675,23693,23765,23787,23916,23925,24070,24082,24122,24166,24182,24192,24221,24298,24325,24403,24470,24488,24507,24596,24663,24733,24787,24827,24863,24957,24986,25018,25038,25114,25155,25205,25254,25288,25303,25344,25392,25423,25503,25548,25639,25702,25742,25815,25871,25985,26046,26089,26135,26201,26241,26271,26293,26414,26567,26582,26640,26729,26776,26833,26863,26936,27058,27142,27219,27384,27425,27518,27551,27571,27626,27762,27801,27858,27878,27937,27952,27978,27994,28049,28071,28151,28281,28315,28393,28436,28478,28567,28587,28677,28690,28805,28851,28865,28993,29053,29100,29114,29154,29341,29559,29605,29635,29664,29741,29810,29858,29948,29976,29936,29820,29749,29724,29662,29623,29600,29413,29181,29137,29111,29068,29019,28934,28857,28839,28753,28688,28664,28581,28518,28458,28415,28366,28297,28223,28124,28067,28007,27980,27967,27944,27936,27877,27834,27763,27633,27587,27567,27542,27507,27408,27221,27143,27098,26952,26884,26845,26792,26769,26675,26627,26580,26416,26390,26293,26248,26239,26144,26114,26059,26002,25910,25818,25768,25717,25644,25626,25526,25477,25407,25346,25305,25294,25282,25239,25160,25139,25041,25021,24993,24984,24934,24839,24811,24780,24709,24656,24539,24499,24483,24436,24378,24303,24271,24206,24189,24181,24154,24119,24073,23954,23919,23865,23766,23696,23680,23640,23602,23537,23511,23461,23425,23371,23215,23151,23082,23035,23002,22943,22899,22829,22824,22814,22691,22614,22593,22516,22485,22420,22371,22341,22323,22268,22207,22194,22141,22109,22058,21991,21957,21946,21862,21816,21807,21770,21691,21608,21549,21468,21450,21352,21276,21086,21080,20921,20896,20864,20824,20699,20622,20592,20561,20460,20401,20306,20250,20214,20092,20053,20035,20009,19969,19965,19914,19867,19834,19809,19708,19629,19551,19482,19456,19381,19244,19212,19109,18971,18882,18855,18809,18700,18668,18632,18528,18472,18417,18388,18315,18299,18252,18160,18132,18081,17920,17891,17852,17811,17704,17637,17609,17557,17525,17401,17369,17320,17267,17244,17200,17162,17126,17090,17035,17018,16950,16800,16772,16741,16636,16541,16477,16432,16343,16329,16306,16239,16215,16114,16092,16047,15849,15798,15764,15685,15481,15370,15342,15337,15323,15304,15260,15198,15155,15128,15035,14914,14864,14846,14833,14794,14751,14677,14592,14529,14422,14410,14338,14254,14196,14160,14134,14004,13963,13901,13871,13827,13740,13687,13643,13516,13422,13222,13220,13142,13113,13092,13032,12844,12819,12801,12733,12683,12595,12557,12475,12463,12426,12395,12350,12305,12252,12244,12171,12154,12118,12077,11952,11910,11885,11777,11674,11640,11565,11563,11494,11394,11357,11241,11193,11147,11117,10962,10895,10861,10833,10624,10580,10496,10424,10392,10282,10262,10094,10078,10035,9981,9946,9938,9838,9810,9797,9747,9718,9689,9668,9582,9545,9462,9379,9365,9267,9184,9071,9013,8979,8892,8826,8785,8651,8615,8601,8538,8535,8503,8489,8464,8424,8375,8345,8327,8310,8268,8131,8047,8016,7982,7782,7636,7616,7585,7496,7465,7408,7322,7260,7133,7084,7041,7004,6962,6903,6900,6860,6810,6792,6659,6621,6608,6527,6402,6246,6203,6113,6044,5908,5896,5762,5720,5704,5672,5493,5349,5303,5231,5180,5140,5000,4933,4893,4881,4818,4604,4544,4511,4426,4359,4215,4124,4036,4002,3988,3963,3903,3868,3839,3748,3743,3709,3643,3558,3516,3484,3432,3379,3251,3140,3134,3058,3011,2981,2934,2923,2884,2849,2825,2793,2663,2613,2504,2477,2377,2323,2275,2245,2207,2154,2148,2063,2030,2019,2005,1926,1912,1888,1802,1719,1688,1610,1603,1492,1371,1327,1208,1162,1096,947,846,832,791,729,645,568,522,489,285,241,121,109,59};
        System.out.println(solution.sumSubarrayMins(arr));

//        double a = (int)Math.pow(10, 9) + 7;
//        System.out.println(a);
//
//        System.out.println(Integer.MAX_VALUE);
    }

//    public int sumSubarrayMins(int[] arr) {
//        int resultSum = 0;
//
//        for (int i = 0; i < arr.length; i++) {
//            int min = Integer.MAX_VALUE;
//            int count = 0;
//            for (int j = i; j < arr.length; j++) {
//                if (arr[j] < min) {
//                    resultSum = (resultSum + count * min) % ((int)Math.pow(10, 9) + 7);
//                    min = arr[j];
//                    count = 0;
//                }
//                count ++;
//
//            }
//            resultSum = (resultSum + count * min) % ((int)Math.pow(10, 9) + 7);
//        }
//        return resultSum;
//    }


    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        long ans = 0;
        final int MOD = 1000000007;
        Deque<Integer> monoStack = new ArrayDeque<>();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            while (!monoStack.isEmpty() && arr[monoStack.peek()] > arr[i]) {
                monoStack.pop();
            }
            int k = monoStack.isEmpty() ? (i + 1) : (i - monoStack.peek());
            dp[i] = k * arr[i] + (monoStack.isEmpty() ? 0 : dp[i - k]);
            ans = (ans + dp[i]) % MOD;
            monoStack.push(i);
        }
        return (int) ans;
    }

}
